import java.util.Arrays;

/**
 * @author wangj881
 * @date 2024-12-09 10:04
 */
public class L151_2 {

    public static void main(String[] args) {
        String s = " the  sky is blue  ";
        String reverseWords = new Solution().reverseWords(s);
        System.out.println(reverseWords);

    }

    static class Solution {
        public String reverseWords(String s) {
            StringBuilder sb = removeSpace(s);
            reverse(sb, 0, sb.length() - 1);
            reverseEach(sb);
            return sb.toString();
        }

        private void reverseEach(StringBuilder sb) {
            int begin = 0;
            for (int i = 0; i < sb.length(); i++) {
                if (sb.charAt(i) == ' ') {
                    reverse(sb, begin, i - 1);
                    begin = i + 1;
                }
            }
            reverse(sb, begin, sb.length() - 1);
        }

        private StringBuilder removeSpace(String s) {
            int start = 0;
            int end = s.length() - 1;
            while (s.charAt(start) == ' ') start++;
            while (s.charAt(end) == ' ') end--;
            StringBuilder sb = new StringBuilder();
            while (start <= end) {
                char c = s.charAt(start);
                if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                    sb.append(c);
                }
                start++;
            }
            return sb;
        }

        private void reverse(StringBuilder chars, int begin, int end) {
            char tmp;
            while (begin < end) {
                tmp = chars.charAt(begin);
                chars.setCharAt(begin, chars.charAt(end));
                chars.setCharAt(end, tmp);
                begin++;
                end--;
            }
        }
    }
}
